// 背包问题
// 给定一个固定大小的背包，背包的容量为 capicity，有一组物品，存在一组物品
    // 存在对应的重量和价值，要求找出最佳的解决方案，使得没报的总重量不超过capitity
    // 而且总价值最大

    // (3,2),(4,3),(5,4)
    // 怎么装，价值最大

    // 1. 如果不能取部分  01背包，要不全拿，要不不拿

    const products = [
        {id:1,v:60,w:10},
        {id:2,v:100,w:20},
        {id:3,v:120,w:30},
    ]

    function backpack(W,products){
        const sorteProducts = products.sort((p1,p2)=>{
            const price1=p1.v/p1.w;
            const price2=p2.v/p2.w;
            if(price1>price2){
                return -1;
            }
            else{
                return 1;
            }
        })

        const result = [];

        let allValue = 0;

        const length = sorteProducts.length;
        for(let i =0;i<length;i++){
            const sorteProduct = sorteProducts[i]
            if(W>=sorteProduct.w){
                result.push({
                    id:sorteProduct.id,
                    take:1
                });
                W=W-sorteProduct.w
                allValue = allValue+sorteProduct.v
            }
            else if(W>0){
                result.push({
                    if:sorteProduct.id,
                    take:W/sorteProduct.w
                })
                allValue = allValue + sorteProduct.v * (W/sorteProduct.w)
                W=0;
            }
            else{
                result.push({
                    id:sorteProduct.id,
                    take:0 
                })
            }

        }
        return {result:result,allValue:allValue}
    }

    console.log(backpack(50,products))